class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1、计算需要反转的次数
        ListNode cur = head;
        int n = 0, cnt = 0;
        while (cur != null) {
            cnt++;
            cur = cur.next;
        }
        n = cnt / k;
        // 2、开始n次翻转，每次翻转k个
        ListNode newHead = new ListNode(-1);
        ListNode prev = head, next = prev.next, tmp = null;
        for (int i = 0; i < n; i++) {
            cur = cur == null ? newHead : tmp;
            for (int j = 0; j < k; j++) {
                if (j == 0) {
                    tmp = prev; // 记录下一次插入的位置
                }
                // 使用头插法
                prev.next = cur.next;
                cur.next = prev;
                // 更新节点指针(cur不能更新)
                prev = next;
                next = next == null ? null : next.next;
            }
        }
        cur = tmp; // 确保cur为新链表的尾节点
        // 3、将剩下的结点拼接上去
        cur.next = prev;
        return newHead.next;
    }
}